<!DOCTYPE HTML>
<html lang="zh-Hans">


<head><meta name="generator" content="Hexo 3.8.0">
    <meta charset="utf-8">
    <meta name="keywords" content="MySQL的InnoDB索引原理详解, java">
    <meta name="description" content="摘要：　　本篇介绍下Mysql的InnoDB索引相关知识，从各种树到索引原理到存储的细节。　　InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM，文档)。本着高效学习的目的，本篇以介绍InnoDB为主，少量涉及M">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <title>MySQL的InnoDB索引原理详解 | 生如夏花</title>
    <link rel="icon" type="image/png" href="/favicon.png">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/font-awesome.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">
    <style type="text/css">
        
    </style>

    <script src="/libs/jquery/jquery-2.2.0.min.js"></script>
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css"></head>


<body>

<header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">生如夏花</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fa fa-navicon"></i></a>
<ul class="right">
    
    <li class="hide-on-med-and-down">
        <a href="/" class="waves-effect waves-light">
            
            <i class="fa fa-home"></i>
            
            <span>主页</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/tags" class="waves-effect waves-light">
            
            <i class="fa fa-tags"></i>
            
            <span>标签</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/categories" class="waves-effect waves-light">
            
            <i class="fa fa-bookmark"></i>
            
            <span>分类</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/archives" class="waves-effect waves-light">
            
            <i class="fa fa-archive"></i>
            
            <span>归档</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/about" class="waves-effect waves-light">
            
            <i class="fa fa-user-circle-o"></i>
            
            <span>关于</span>
        </a>
    </li>
    
    <li>
        <a href="#searchModal" class="modal-trigger waves-effect waves-light">
            <i id="searchIcon" class="fa fa-search" title="Search"></i>
        </a>
    </li>
</ul>

<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">生如夏花</div>
        <div class="logo-desc">
            
            从来没有真正的绝境，只有心灵的迷途
            
        </div>
    </div>

    

    <ul class="menu-list mobile-menu-list">
        
        <li>
            <a href="/" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-home"></i>
                
                主页
            </a>
        </li>
        
        <li>
            <a href="/tags" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-tags"></i>
                
                标签
            </a>
        </li>
        
        <li>
            <a href="/categories" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-bookmark"></i>
                
                分类
            </a>
        </li>
        
        <li>
            <a href="/archives" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-archive"></i>
                
                归档
            </a>
        </li>
        
        <li>
            <a href="/about" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-user-circle-o"></i>
                
                关于
            </a>
        </li>
        
        
        <li><div class="divider"></div></li>
        <li>
            <a href="https://github.com/jackliu7" class="waves-effect waves-light" target="_blank">
                <i class="fa fa-github-square fa-fw"></i>Fork Me
            </a>
        </li>
        
    </ul>
</div>

        </div>

        
            <style>
    .nav-transparent .github-corner {
        display: none !important;
    }

    .github-corner {
        position: absolute;
        z-index: 10;
        top: 0;
        right: 0;
        border: 0;
        transform: scale(1.1);
    }

    .github-corner svg {
        color: #0f9d58;
        fill: #fff;
        height: 64px;
        width: 64px;
    }

    .github-corner:hover .octo-arm {
        animation: a 0.56s ease-in-out;
    }

    .github-corner .octo-arm {
        animation: none;
    }

    @keyframes a {
        0%,
        to {
            transform: rotate(0);
        }
        20%,
        60% {
            transform: rotate(-25deg);
        }
        40%,
        80% {
            transform: rotate(10deg);
        }
    }
</style>

<a href="https://github.com/jackliu7" class="github-corner tooltipped hide-on-med-and-down" target="_blank" data-tooltip="Fork Me" data-position="left" data-delay="50">
    <svg viewbox="0 0 250 250" aria-hidden="true">
        <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"/>
        <path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"/>
        <path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"/>
    </svg>
</a>
        
    </nav>

</header>





<div class="bg-cover pd-header post-cover" style="background-image: url('/medias/featureimages/11.jpg')">
    <div class="container">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <div class="description center-align post-title">
                        MySQL的InnoDB索引原理详解
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>



<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        margin: 35px 0 15px 0;
        padding-left: 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #toc-content .is-active-link::before {
        background-color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 20px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/tags/Mysql/" target="_blank">
                                <span class="chip bg-color">Mysql</span>
                            </a>
                        
                            <a href="/tags/InnoDB/" target="_blank">
                                <span class="chip bg-color">InnoDB</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fa fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/categories/数据库/" class="post-category" target="_blank">
                                数据库
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                <div class="post-date info-break-policy">
                    <i class="fa fa-calendar-minus-o fa-fw"></i>Publish Date:&nbsp;&nbsp;
                    2019-05-14
                </div>

                
                    
                    <div class="info-break-policy">
                        <i class="fa fa-file-word-o fa-fw"></i>Word Count:&nbsp;&nbsp;
                        5k
                    </div>
                    

                    
                    <div class="info-break-policy">
                        <i class="fa fa-clock-o fa-fw"></i>Read Times:&nbsp;&nbsp;
                        17 Min
                    </div>
                    
                
				
				
                    <div id="busuanzi_container_page_pv" class="info-break-policy">
                        <i class="fa fa-eye fa-fw"></i>Read Count:&nbsp;&nbsp;
                        <span id="busuanzi_value_page_pv"></span>
                    </div>
				
            </div>
        </div>
        <hr class="clearfix">
        <div class="card-content article-card-content">
            <div id="articleContent">
                <div class="postbody"><br><h3>摘要：</h3><br><p>　　本篇介绍下Mysql的InnoDB索引相关知识，从各种树到索引原理到存储的细节。</p><br><a id="more"></a><br><p>　　InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM，<a href="http://dev.mysql.com/doc/refman/5.5/en/server-options.html#option_mysqld_default-storage-engine" target="_blank">文档</a>)。本着高效学习的目的，本篇以介绍InnoDB为主，少量涉及MyISAM作为对比。</p><br><p>　　这篇文章是我在学习过程中总结完成的，内容主要来自书本和博客(参考文献会给出)，过程中加入了一些自己的理解，描述不准确的地方烦请指出。</p><br><h3>　　1 各种树形结构</h3><br><p>　　本来不打算从二叉搜索树开始，因为网上已经有太多相关文章，但是考虑到清晰的图示对理解问题有很大帮助，也为了保证文章完整性，最后还是加上了这部分。</p><br><p>　　先看看几种树形结构：</p><br><p>　　1 搜索二叉树：每个节点有两个子节点，数据量的增大必然导致高度的快速增加，显然这个不适合作为大量数据存储的基础结构。</p><br><p>　　2 B树：一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 &lt;= j &lt;= m - 1；一个节点的子节点数量会比关键字个数多1，这样关键字就变成了子节点的分割标志。一般会在图示中把关键字画到子节点中间，非常形象，也容易和后面的B+树区分。由于数据同时存在于叶子节点和非叶子结点中，无法简单完成按顺序遍历B树中的关键字，必须用中序遍历的方法。</p><br><p>　　3 B+树：一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 &lt;= j &lt;= m；子树的个数最多可以与关键字一样多。非叶节点存储的是子树里最小的关键字。同时数据节点只存在于叶子节点中，且叶子节点间增加了横向的指针，这样顺序遍历所有数据将变得非常容易。</p><br><p>　　4 B<em>树：一棵m阶B树是一棵平衡的m路搜索树。最重要的两个性质是1每个非根节点所包含的关键字个数 j 满足：┌m2/3┐ - 1 &lt;= j &lt;= m；2非叶节点间添加了横向指针。</em></p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091300383225.PNG" alt></p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091308112206.PNG" alt></p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091317678858.PNG" alt></p><br><p>　　B/B+/B三种树有相似的操作，比如检索/插入/删除节点。这里只重点关注插入节点的情况，且只分析他们在当前节点已满情况下的插入操作，因为这个动作稍微复杂且能充分体现几种树的差异。与之对比的是检索节点比较容易实现，而删除节点只要完成与插入相反的过程即可（在实际应用中删除并不是插入的完全逆操作，往往只删除数据而保留下空间为后续使用）。</p><br><p>　　先看B树的分裂，下图的红色值即为每次新插入的节点。每当一个节点满后，就需要发生分裂（分裂是一个递归过程，参考下面7的插入导致了两层分裂），由于B树的非叶子节点同样保存了键值，所以已满节点分裂后的值将分布在三个地方：1原节点，2原节点的父节点，3原节点的新建兄弟节点（参考5，7的插入过程）。分裂有可能导致树的高度增加（参考3，7的插入过程），也可能不影响树的高度（参考5，6的插入过程）。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091402944893.PNG" alt></p><br><p>　　B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟节点的指针。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091412822063.PNG" alt></p><br><p>　　B<em>树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）。如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。可以看到B</em>树的分裂非常巧妙，因为B<em>树要保证分裂后的节点还要2/3满，如果采用B+树的方法，只是简单的将已满的节点一分为二，会导致每个节点只有1/2满，这不满足B</em>树的要求了。所以B<em>树采取的策略是在本节点满后，继续插入兄弟节点（这也是为什么B</em>树需要在非叶子节点加一个兄弟间的链表），直到把兄弟节点也塞满，然后拉上兄弟节点一起凑份子，自己和兄弟节点各出资1/3成立新节点，这样的结果是3个节点刚好是2/3满，达到B<em>树的要求，皆大欢喜。</em></p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091423290770.PNG" alt></p><br><p>　　B+树适合作为数据库的基础结构，完全是因为计算机的内存-机械硬盘两层存储结构。内存可以完成快速的随机访问（随机访问即给出任意一个地址，要求返回这个地址存储的数据）但是容量较小。而硬盘的随机访问要经过机械动作（1磁头移动 2盘片转动），访问效率比内存低几个数量级，但是硬盘容量较大。典型的数据库容量大大超过可用内存大小，这就决定了在B+树中检索一条数据很可能要借助几次磁盘IO操作来完成。如下图所示：通常向下读取一个节点的动作可能会是一次磁盘IO操作，不过非叶节点通常会在初始阶段载入内存以加快访问速度。同时为提高在节点间横向遍历速度，真实数据库中可能会将图中蓝色的CPU计算/内存读取优化成二叉搜索树（InnoDB中的page directory机制）。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091432578535.PNG" alt></p><br><p>　　真实数据库中的B+树应该是非常扁平的，可以通过向表中顺序插入足够数据的方式来验证InnoDB中的B+树到底有多扁平。我们通过如下图的CREATE语句建立一个只有简单字段的测试表，然后不断添加数据来填充这个表。通过下图的统计数据（来源见参考文献1）可以分析出几个直观的结论，这几个结论宏观的展现了数据库里B+树的尺度。</p><br><p>　　1 每个叶子节点存储了468行数据，每个非叶子节点存储了大约1200个键值，这是一棵平衡的1200路搜索树！</p><br><p>　　2 对于一个22.1G容量的表，也只需要高度为3的B+树就能存储了，这个容量大概能满足很多应用的需要了。如果把高度增大到4，则B+树的存储容量立刻增大到25.9T之巨！</p><br><p>　　3 对于一个22.1G容量的表，B+树的高度是3，如果要把非叶节点全部加载到内存也只需要少于18.8M的内存（如何得出的这个结论？因为对于高度为2的树，1203个叶子节点也只需要18.8M空间，而22.1G从良表的高度是3，非叶节点1204个。同时我们假设叶子节点的尺寸是大于非叶节点的，因为叶子节点存储了行数据而非叶节点只有键和少量数据。），只使用如此少的内存就可以保证只需要一次磁盘IO操作就检索出所需的数据，效率是非常之高的。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091442379434.PNG" alt></p><br><h3>　　2 Mysql的存储引擎和索引</h3><br><p>　　可以说数据库必须有索引，没有索引则检索过程变成了顺序查找，O(n)的时间复杂度几乎是不能忍受的。我们非常容易想象出一个只有单关键字组成的表如何使用B+树进行索引，只要将关键字存储到树的节点即可。当数据库一条记录里包含多个字段时，一棵B+树就只能存储主键，如果检索的是非主键字段，则主键索引失去作用，又变成顺序查找了。这时应该在第二个要检索的列上建立第二套索引。 &nbsp;这个索引由独立的B+树来组织。有两种常见的方法可以解决多个B+树访问同一套表数据的问题，一种叫做聚簇索引（clustered index&nbsp;），一种叫做非聚簇索引（secondary index）。这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。对于聚簇索引存储来说，行数据和主键B+树存储在一起，辅助键B+树只存储辅助键和主键，主键和非主键B+树几乎是两种类型的树。对于非聚簇索引存储来说，主键B+树在叶子节点存储指向真正数据行的指针，而非主键。</p><br><p>　　InnoDB使用的是聚簇索引，将主键组织到一棵B+树中，而行数据就储存在叶子节点上，若使用”where id = 14”这样的条件查找主键，则按照B+树的检索算法即可查找到对应的叶节点，之后获得行数据。若对Name列进行条件搜索，则需要两个步骤：第一步在辅助索引B+树中检索Name，到达其叶子节点获取对应的主键。第二步使用主键在主索引B+树种再执行一次B+树检索操作，最终到达叶子节点即可获取整行数据。</p><br><p>　　MyISM使用的是非聚簇索引，非聚簇索引的两棵B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独立的，通过辅助键检索无需访问主键的索引树。</p><br><p>　　为了更形象说明这两种索引的区别，我们假想一个表如下图存储了4行数据。其中Id作为主索引，Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091453469704.PNG" alt></p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091503903957.PNG" alt></p><br><p>　　我们重点关注聚簇索引，看上去聚簇索引的效率明显要低于非聚簇索引，因为每次使用辅助索引检索都要经过两次B+树查找，这不是多此一举吗？聚簇索引的优势在哪？</p><br><p>　　1 由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键Id来组织数据，获得数据更快。</p><br><p>　　2 辅助索引使用主键作为”指针” 而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作，使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是InnoDB在移动行时无须更新辅助索引中的这个”指针”。也就是说行的位置（实现中通过16K的Page来定位，后面会涉及）会随着数据库里数据的修改而发生变化（前面的B+树节点分裂以及Page的分裂），使用聚簇索引就可以保证不管这个主键B+树的节点如何变化，辅助索引树都不受影响。</p><br><h3>　　3 Page结构</h3><br><p>　　如果说前面的内容偏向于解释原理，那后面就开始涉及具体实现了。</p><br><p>　　理解InnoDB的实现不得不提Page结构，Page是整个InnoDB存储的最基本构件，也是InnoDB磁盘管理的最小单位，与数据库相关的所有内容都存储在这种Page结构里。Page分为几种类型，常见的页类型有数据页（B-tree Node）Undo页（Undo Log Page）系统页（System Page） 事务数据页（Transaction System Page）等。单个Page的大小是16K（编译宏UNIV_PAGE_SIZE控制），每个Page使用一个32位的int值来唯一标识，这也正好对应InnoDB最大64TB的存储容量（16Kib  2^32 = 64Tib）。一个Page的基本结构如下图所示：</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091512695110.PNG" alt></p><br><p>　　每个Page都有通用的头和尾，但是中部的内容根据Page的类型不同而发生变化。Page的头部里有我们关心的一些数据，下图把Page的头部详细信息显示出来：</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091523976520.PNG" alt></p><br><p>&nbsp;</p><br><p>　　我们重点关注和数据组织结构相关的字段：Page的头部保存了两个指针，分别指向前一个Page和后一个Page，头部还有Page的类型信息和用来唯一标识Page的编号。根据这两个指针我们很容易想象出Page链接起来就是一个双向链表的结构。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091532199537.PNG" alt></p><br><p>　　再看看Page的主体内容，我们主要关注行数据和索引的存储，他们都位于Page的User Records部分，User Records占据Page的大部分空间，User Records由一条一条的Record组成，每条记录代表索引树上的一个节点（非叶子节点和叶子节点）。在一个Page内部，单链表的头尾由固定内容的两条记录来表示，字符串形式的”Infimum”代表开头，”Supremum”代表结尾。这两个用来代表开头结尾的Record存储在System Records的段里，这个System Records和User Records是两个平行的段。InnoDB存在4种不同的Record，它们分别是1主键索引树非叶节点 2主键索引树叶子节点 3辅助键索引树非叶节点 4辅助键索引树叶子节点。这4种节点的Record格式有一些差异，但是它们都存储着Next指针指向下一个Record。后续我们会详细介绍这4种节点，现在只需要把Record当成一个存储了数据同时含有Next指针的单链表节点即可。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091541081339.PNG" alt></p><br><p>　　User Record在Page内以单链表的形式存在，最初数据是按照插入的先后顺序排列的，但是随着新数据的插入和旧数据的删除，数据物理顺序会变得混乱，但他们依然保持着逻辑上的先后顺序。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091551111655.PNG" alt></p><br><p>　　把User Record的组织形式和若干Page组合起来，就看到了稍微完整的形式。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091600910753.PNG" alt></p><br><p>　　现在看下如何定位一个Record：</p><br><p>　　1 通过根节点开始遍历一个索引的B+树，通过各层非叶子节点最终到达一个Page，这个Page里存放的都是叶子节点。</p><br><p>　　2 在Page内从”Infimum”节点开始遍历单链表（这种遍历往往会被优化），如果找到该键则成功返回。如果记录到达了”supremum”，说明当前Page里没有合适的键，这时要借助Page的Next Page指针，跳转到下一个Page继续从”Infimum”开始逐个查找。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091608678237.PNG" alt></p><br><p>　　详细看下不同类型的Record里到底存储了什么数据，根据B+树节点的不同，User Record可以被分成四种格式，下图种按照颜色予以区分。</p><br><p>　　<strong>1 主索引树非叶节点（绿色）</strong></p><br><p>　　1 子节点存储的主键里最小的值（Min Cluster Key on Child），这是B+树必须的，作用是在一个Page里定位到具体的记录的位置。</p><br><p>　　2 最小的值所在的Page的编号（Child Page Number），作用是定位Record。</p><br><p>　　<strong>2 主索引树叶子节点（黄色）</strong></p><br><p>　　1 主键（Cluster Key Fields），B+树必须的，也是数据行的一部分</p><br><p>　　2 除去主键以外的所有列（Non-Key Fields），这是数据行的除去主键的其他所有列的集合。</p><br><p>　　这里的1和2两部分加起来就是一个完整的数据行。</p><br><p>　　<strong>3 辅助索引树非叶节点非（蓝色）</strong></p><br><p>　　1 子节点里存储的辅助键值里的最小的值（Min Secondary-Key on Child），这是B+树必须的，作用是在一个Page里定位到具体的记录的位置。</p><br><p>　　2 主键值（Cluster Key Fields），非叶子节点为什么要存储主键呢？因为辅助索引是可以不唯一的，但是B+树要求键的值必须唯一，所以这里把辅助键的值和主键的值合并起来作为在B+树中的真正键值，保证了唯一性。但是这也导致在辅助索引B+树中非叶节点反而比叶子节点多了4个字节。（即下图中蓝色节点反而比红色多了4字节）</p><br><p>　　3 最小的值所在的Page的编号（Child Page Number），作用是定位Record。</p><br><p>　　<strong>4 辅助索引树叶子节点（红色）</strong></p><br><p>　　1 辅助索引键值（Secondary Key Fields），这是B+树必须的。</p><br><p>　　2 主键值（Cluster Key Fields），用来在主索引树里再做一次B+树检索来找到整条记录。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091620754769.PNG" alt></p><br><p>　　下面是本篇最重要的部分了，结合B+树的结构和前面介绍的4种Record的内容，我们终于可以画出一幅全景图。由于辅助索引的B+树与主键索引有相似的结构，这里只画出了主键索引树的结构图，只包含了”主键非叶节点”和”主键叶子节点”两种节点，也就是上图的的绿色和黄色的部分。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091631948071.PNG" alt></p><br><p>　　把上图还原成下面这个更简洁的树形示意图，这就是B+树的一部分。注意Page和B+树节点之间并没有一一对应的关系，Page只是作为一个Record的保存容器，它存在的目的是便于对磁盘空间进行批量管理，上图中的编号为47的Page在树形结构上就被拆分成了两个独立节点。</p><br><p><img src="http://www.admin10000.com/UploadFiles/Document/201410/27/20141027091642165340.PNG" alt></p><br><p>　　至此本篇就算结束了，本篇只是对InnoDB索引相关的数据结构和实现进行了一些梳理总结，并未涉及到Mysql的实战经验。这主要是基于几点原因：</p><br><p>　　1 原理是基石，只有充分了解InnoDB索引的工作方式，我们才有能力高效的使用好它。</p><br><p>　　2 原理性知识特别适合使用图示，我个人非常喜欢这种表达方式。</p><br><p>　　3 关于InnoDB优化，在《高性能Mysql》里有更加全面的介绍，对优化Mysql感兴趣的同学完全可以自己获取相关知识，我自己的积累还未达到能分享这些内容的地步。</p><br><p>　　另：对InnoDB实现有更多兴趣的同学可以看看Jeremy Cole的博客（参考文献三篇文章的来源），这位老兄曾先后在Mysql，Yahoo，Twitter，Google从事数据库相关工作，他的文章非常棒！</p></div><div id="MySignature"></div>






            </div>
            <hr>

            

            <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">

<div id="article-share">
    
    <div class="social-share" data-disabled="qzone" data-wechat-qrcode-helper="<p>微信里点“发现”->“扫一扫”二维码便可查看分享。</p>"></div>
    
</div>

<script src="/libs/share/js/social-share.min.js"></script>

            


        </div>
    </div>

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6 overflow-policy" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fa fa-chevron-left"></i>&nbsp;Previous</div>
            <div class="card">
                <a href="/tomcat安装SSL安全证书.html">
                    <div class="card-image">
                        
                        
                        <img src="/medias/featureimages/16.jpg" class="responsive-img" alt="tomcat安装SSL安全证书">
                        
                        <span class="card-title">tomcat安装SSL安全证书</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            
首先，不知道你有没有发现，有时你在浏览器访问一个网址时，例如（www.hzelin.top）,你会发现网址左边是个 X不安全（表示该链接不安全，使用的是http未加密协议），而有时你访问一个网址的时候发现地址左边是https://（表示该
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="fa fa-clock-o fa-fw icon-date"></i>2019-05-17
                        </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/tomcat/" class="post-category" target="_blank">
                                    tomcat
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/SSL/" target="_blank">
                        <span class="chip bg-color">SSL</span>
                    </a>
                    
                    <a href="/tags/tomcat/" target="_blank">
                        <span class="chip bg-color">tomcat</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6 overflow-policy" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                Next&nbsp;<i class="fa fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/MySql数据库知识点总结02-索引.html">
                    <div class="card-image">
                        
                        
                        <img src="/medias/featureimages/23.jpg" class="responsive-img" alt="MySql数据库知识点总结02-索引">
                        
                        <span class="card-title">MySql数据库知识点总结02-索引</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            数据库索引是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。
索引是什么？&nbsp; &nbsp; &nbsp;数据库索引是数据库管理系统中一个排序的数据结构，以协助快速查询、
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="fa fa-clock-o fa-fw icon-date"></i>2019-05-14
                            </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/数据库/" class="post-category" target="_blank">
                                    数据库
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Mysql/" target="_blank">
                        <span class="chip bg-color">Mysql</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>
</div>



    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget">
            <div class="toc-title"><i class="fa fa-list-alt"></i>&nbsp;&nbsp;TOC</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fa fa-list"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            // headingsOffset: -205,
            headingSelector: 'h2, h3, h4'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h2, h3, h4').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).slideUp(500);
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).slideDown(500);
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>
    

</main>


<footer class="page-footer bg-color">
    <div class="container row center-align">
        <div class="col s12 m8 l8 copy-right">
            

            
			
                <br>
                
                <span id="busuanzi_container_site_pv">
                    <i class="fa fa-heart-o"></i>
                    本站总访问量 <span id="busuanzi_value_site_pv" class="white-color"></span>
                </span>
                
                
                <span id="busuanzi_container_site_uv">
                    <i class="fa fa-users"></i>
                    次,&nbsp;访客数 <span id="busuanzi_value_site_uv" class="white-color"></span> 人
                </span>
                
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/jackliu7" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fa fa-github"></i>
    </a>



    <a href="mailto:liudazh@outlook.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fa fa-envelope-open"></i>
    </a>



    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2263132654" class="tooltipped" data-tooltip="QQ联系我: 2263132654" data-position="top" data-delay="50">
        <i class="fa fa-qq"></i>
    </a>


</div>
    </div>
</footer>

<div class="progress-bar"></div>


<!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fa fa-search"></i>&nbsp;&nbsp;Search</span>
            <input type="search" id="searchInput" name="s" placeholder="Please enter a search keyword" class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script src="/js/search.js"></script>
<script type="text/javascript">
$(function () {
    searchFunc("/" + "search.xml", 'searchInput', 'searchResult');
});
</script>
<!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fa fa-angle-up"></i>
    </a>
</div>


<script src="/libs/materialize/materialize.min.js"></script>
<script src="/libs/masonry/masonry.pkgd.min.js"></script>
<script src="/libs/aos/aos.js"></script>
<script src="/libs/scrollprogress/scrollProgress.min.js"></script>
<script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
<script src="/js/matery.js"></script>

<!-- Global site tag (gtag.js) - Google Analytics -->



    <script src="/libs/others/clicklove.js"></script>


    <script async src="/libs/others/busuanzi.pure.mini.js"></script>


</body>
</html>